import randomList.Node;

import java.util.HashMap;

public class Solution138 {
    HashMap<Node, Node> map = new HashMap<>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node n = map.get(head);
        if (n != null) {
            return n;
        }
        Node copy = new Node(head.val);
        map.put(head, copy);
        copy.next = copyRandomList(head.next);
        copy.random = copyRandomList(head.random);
        return copy;
    }
}
